An Đông được thành lập lần đầu vào năm 1934 trong vai trò là một đơn vị hành chính của Mãn Châu Quốc, một chính phủ thân Nhật. Khi đó, tỉnh Phụng Thiên đã được chia tách thành ba phần: tỉnh An Đông, tỉnh Phụng Thiên và Cẩm Châu. Năm 1939, An Đông lại tiếp tục bị chia tách thành tỉnh An Đông mới và tỉnh Thông Hóa.

Vào cuối Chiến tranh thế giới thứ hai, Trung Hoa Dân Quốc đã tấn công Mãn Châu Quốc, Quốc Dân đảng sau đó đã hợp nhất An Đông và Thông Hóa, và tiếp tục gọi đây là tỉnh An Đông. Tuy nhiên, sau khi Cộng hòa Nhân dân Trung Hoa ra đời, tỉnh An Đông bị bãi bỏ vào năm 1954, và lãnh thổ của tỉnh được phân chia giữa hai tỉnh Liêu Ninh và Cát Lâm.